package com.wyr.leetcode.step2.dfs;

/**
 * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
 * https://leetcode.cn/problems/same-tree/description/?envType=problem-list-v2&envId=depth-first-search
 */
public class IsSameTree {
    static StringBuilder sb1 = new StringBuilder();
    static StringBuilder sb2 = new StringBuilder();

    public static boolean isSameTree(TreeNode p, TreeNode q) {
        dfs(p, sb1);
        dfs(q, sb2);
        return sb1.toString().equals(sb2.toString());
    }

    public static void dfs(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append('#').append(',');
            return;
        }
        sb.append(root.val).append(',');
        dfs(root.left, sb);
        dfs(root.right, sb);
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);

        TreeNode root2 = new TreeNode(1);
        root2.right = new TreeNode(2);

        System.out.println(isSameTree(root1, root2));

    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
